/**
 * 最⼩找零纸币数。币种含：1、2、5、10、20、30、50、100元
 * # Arguments
 * * `amount` - 金额
 * # Returns
 * 纸币数
 * # Examples
```
let p = solution4::rec_mc::dp_rec_mc(24);
assert_eq!(p, 3);
```
 */
pub fn dp_rec_mc(amount: u32) -> u32 {
    dp_rec_mc_general(amount, &[1, 2, 5, 10, 20, 30, 50, 100]).unwrap()
}

/**
 * 最⼩找零纸币数。币种含：1、2、5、10、20、30、50、100元
 * 这里给出通用的dp方法，并考虑了找不开的可能
 * # Arguments
 * * `amount` - 金额
 * # Returns
 * 纸币数
 * # Examples
```
let p = solution4::rec_mc::dp_rec_mc_general(24, &vec[1, 2, 5, 10, 20, 30, 50, 100]);
assert_eq!(p, Some(3));
```
 */
pub fn dp_rec_mc_general(amount: u32, units: &[u32]) -> Option<u32> {
    let mut counts = vec![None; (amount + 1) as usize];
    counts[0] = Some(0);
    for current_amount in 1..=amount {
        counts[current_amount as usize] = units
            .iter()
            .filter(|unit| {
                (current_amount >= **unit) && counts[(current_amount - **unit) as usize].is_some()
            })
            .map(|unit| counts[(current_amount - *unit) as usize].unwrap() + 1)
            .min()
    }
    counts[amount as usize]
}
/**
 * 最⼩找零纸币数。币种含：1、2、5、10、20、30、50、100元
 * 因为题目给定的金额比较整齐，完全可以枚举出来
 * # Arguments
 * * `amount` - 金额
 * # Returns
 * 纸币数
 * # Examples
```
let p = solution4::rec_mc::dp_rec_mc(24);
assert_eq!(p, 3);
```
 */
#[allow(dead_code)]
pub fn rec_mc_simple(amount: u32) -> u32 {
    let mut amount = amount;
    let mut count = amount / 100;
    amount = amount % 100;
    count += match amount / 10 {
        0 => 0,
        4 | 6 | 7 | 8 => 2,
        9 => 3,
        _ => 1,
    };
    amount = amount % 10;
    count += match amount {
        0 => 0,
        3 | 4 | 6 => 2,
        8 | 9 => 3,
        _ => 1,
    };
    count
}
